class TreeNode {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

//1.前序序列
const preOrderList = ["A", "B", "D", "H", "I", "E", "C", "F", "G"];
//2. 中序遍历
const inOrderList = ["H", "D", "I", "B", "E", "A", "F", "C", "G"];
//3. 后序遍历
const postOrderList = ["H", "I", "D", "E", "B", "F", "G", "C", "A"];


//根据前序序列和中序序列还原二叉树
function buildTree(preOrderList,inOrderList){
    //1.序列为空，不存在树
    if(preOrderList.length===0||inOrderList.length===0){
        return null
    }
    //2.序列不相等，无法构建
    if(preOrderList.length!==inOrderList.length){
        return null
    }

    //前序序列第一个值是根节点
    const rootValue= preOrderList[0]
    const root = new TreeNode(rootValue)

    if(preOrderList.length===1){
        return root
    }
    //在中序中寻找根节点下标
    const rootIndex=inOrderList.indexOf(rootValue)
    if(rootIndex===-1){
        throw new Error(`值为：${rootValue} 的节点在中序列表中未找到，无法构建`)
    }
    //分离中序中的左右子树
    const leftInOrderList=inOrderList.slice(0,rootIndex)
    const rightInOrderList=inOrderList.slice(rootIndex+1)

    //得到左子树长度
    const leftTreeSize=leftInOrderList.length

    //根据长度分离
    const leftPreOrderList=preOrderList.slice(1,leftTreeSize+1)
    const rightPreOrderList=preOrderList.slice(leftTreeSize+1)

    //递归调用
    root.left=buildTree(leftPreOrderList,leftInOrderList)
    root.right=buildTree(rightPreOrderList,rightInOrderList)
    return root
}

//根据后续序列和中序序列还原二叉树
function buildTreeByPostAndIn(postOrderList,inOrderList){
    //1.序列为空，不存在树
    if(postOrderList.length===0||inOrderList.length===0){
        return null
    }
    //2.序列不相等，无法构建
    if(postOrderList.length!==inOrderList.length){
        return null
    }
    let root= new TreeNode(postOrderList[postOrderList.length-1])
    if(postOrderList.length===1){
        return root
    }

    //得到根节点的值
    const rootValue=postOrderList[postOrderList.length-1]
    //得到中序中根节点位置
    const rootIndex=inOrderList.indexOf(rootValue)
    if(rootIndex===-1){
        throw new Error(`值为：${rootValue} 的节点在中序列表中未找到，无法构建`)
    }
    //拆分中序遍历的左右子树
    const leftInOrderList=inOrderList.slice(0,rootIndex)
    const rightInOrderList=inOrderList.slice(rootIndex+1)
    //得到左子树长度
    const leftSize=leftInOrderList.length
    //拆分后序遍历的左子树和右子树
    const leftPostOrderList=postOrderList.slice(0,leftSize)
    const rightPostOrderList=postOrderList.slice(leftInOrderList.length, -1)

    //递归调用
    root.left=buildTreeByPostAndIn(leftPostOrderList,leftInOrderList)
    root.right=buildTreeByPostAndIn(rightPostOrderList,rightInOrderList)
    return root

}

// let root=buildTree(preOrderList,inOrderList)
let root=buildTreeByPostAndIn(postOrderList,inOrderList)
//前序遍历
function preOrder(root){
    if(root===null) return;
    console.log(root.value);
    preOrder(root.left)
    preOrder(root.right)
}
/*
 *        A
 *      /   \
 *     B     C
 *    / \   / \
 *   D   E F   G
 *  / \
 * H   I
 */
preOrder(root)



